package cn.zifangsky.heap.questions;

import cn.zifangsky.queue.PriorityQueue;
import org.junit.Test;

import java.util.Arrays;
import java.util.Collection;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * 求很大一个的乱序序列的中位元素？
 *
 * @author zifangsky
 * @date 2020/5/15
 * @since 1.0.0
 */
public class Problem_002_Median {
    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        //1. 生成 1~100 的整数
        Integer[] arr = IntStream.rangeClosed(1, 100).boxed().toArray(Integer[]::new);

        //2. 将数组的顺序打乱
        shuffle(arr);

        //3. 求中位元素
        Solution<Integer> solution = new Solution<>();
        solution.addAll(Arrays.asList(arr));
        System.out.println("数组中的中位元素是：" + solution.getMedian());
    }


    static class Solution<T extends Comparable<? super T>> {
        /**
         * 优先队列（最大堆）
         */
        private PriorityQueue<T> maxQueue;

        /**
         * 优先队列（最小堆）
         */
        private PriorityQueue<T> minQueue;

        /**
         * 当前中位数
         */
        private T median;

        public Solution() {
            this.maxQueue = new PriorityQueue<T>(PriorityQueue.Mode.MAX);
            this.minQueue = new PriorityQueue<T>(PriorityQueue.Mode.MIN);
        }

        /**
         * 添加一个集合进来
         */
        public void addAll(Collection<? extends T> c){
            for(T e : c){
                this.add(e);
            }
        }

        /**
         * 往队列中添加新值
         */
        public void add(T data){
            if(data == null){
                return;
            }

            //1. 如果当前中位数没值，则直接复制给中位数
            if(this.median == null){
                this.median = data;
                return;
            }

            //2. 如果新值等于中位数，则不作处理
            if(data.compareTo(this.median) == 0){
                return;
            }

            //3. 如果新值大于中位数，则放入最小堆，相反放入最大堆
            if(data.compareTo(this.median) > 0){
                this.minQueue.push(data);
            }else{
                this.maxQueue.push(data);
            }

            //4. 如果两个堆的数目相差超过2，则需要重新平衡两个堆
            if(this.maxQueue.size() - this.minQueue.size() >= 2){
                //4.1 将中位数插入到最小堆
                this.minQueue.push(this.median);
                //4.2 将最大堆出队并设置为新的中位数
                this.median = this.maxQueue.pop();
            }else if(this.minQueue.size() - this.maxQueue.size() >= 2){
                //4.1 将中位数插入到最大堆
                this.maxQueue.push(this.median);
                //4.2 将最小堆出队并设置为新的中位数
                this.median = this.minQueue.pop();
            }
        }

        /**
         * 返回中位元素
         */
        public T getMedian(){
            return this.median;
        }
    }

    /**
     * 洗牌
     */
    private void shuffle(Integer[] arr){
        if(arr == null || arr.length < 1){
            return;
        }
        Random rnd = new Random();

        for(int i = (arr.length -1); i > 0; i--){
            swap(arr, i, rnd.nextInt(i));
        }
    }

    private void swap(Integer[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
